package easy.路径总和;


import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> que_node = new LinkedList<>();
        Queue<Integer> que_val = new LinkedList<>();
        que_node.offer(root);
        que_val.offer(root.val);
        while (!que_node.isEmpty()) {
            TreeNode node = que_node.poll();
            Integer value = que_val.poll();
            //确保是根节点到叶子结点求和
            if (node.left == null && node.right == null) {
                if (value == targetSum) {
                    return true;
                }
                continue;
            }
            if (node.left != null) {
                que_node.offer(node.left);
                que_val.offer(node.left.val + value);
            }
            if (node.right != null) {
                que_node.offer(node.right);
                que_val.offer(node.right.val + value);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)), null),
                new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
        int targetSum = 22;
        TreeNode root2 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        int targetSum2 = 5;
        Solution solution = new Solution();
        System.out.println(solution.hasPathSum(root, targetSum));
        System.out.println(solution.hasPathSum(root2, targetSum2));
    }
}
